package chromosomes;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

import logic.Square;
import logic.Sudoku;

/**
 * class Geneticos
 * 
 * @author Marco Gallardo Casu
 * @author Miguel Cisneros Rojas
 * 
 */
public class GeneticAlgorithm {

	private static final int NUMS = 9;

	private int population;
	private double crossover;
	private double mutation;
	private CrossoverFunction crossoverFunction;
	private MutationFunction mutFunction;
	private TypeSelection typeSelection;
	private boolean[][] blocked;

	private ArrayList<Chromosome> chromosomes;

	// Roulette
	private static int n; // N to reproduction
	private static int x; // X to keep (elitism)
	// Torunament
	private static int k; // Iterations of tournament
	private static int z = 3; // Z elements for mini-tournament
	// Global fitness
	private static double totalFitness;

	public GeneticAlgorithm(int population, double crossover, double mutation,
			TypeSelection typeSelection, int[][] genes, boolean elitism,
			CrossoverFunction crossoverFunction, MutationFunction mutfunction,
			boolean[][] blocked) {
		this.population = population;
		this.crossover = crossover;
		this.mutation = mutation;
		this.typeSelection = typeSelection;
		this.crossoverFunction = crossoverFunction;
		this.mutFunction = mutfunction;
		this.blocked = blocked;
		this.chromosomes = generateRandomPopulation(genes);
		if (elitism) {
			GeneticAlgorithm.x = population / 20;

		} else {
			GeneticAlgorithm.x = 0;
		}
		GeneticAlgorithm.n = population - x;
		GeneticAlgorithm.k = population - x;
	}

	private ArrayList<Chromosome> generateRandomPopulation(int[][] genes) {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(population);
		for (int chromosome = 0; chromosome < population; chromosome++) {
			add(list, new Chromosome(genes, blocked));
		}
		return list;
	}

	public Chromosome getBest() {
		try {
			return (Chromosome) chromosomes.get(0).clone();
		} catch (CloneNotSupportedException e) {
			System.err.println(e.getMessage());
		}
		return null;
	}

	public double getBestFitness() {
		return chromosomes.get(0).getFitness();
	}

	public double getAverageGen() {
		double average = 0;

		for (Chromosome c : chromosomes) {
			average += c.getFitness();
		}

		average /= chromosomes.size();
		return average;
	}

	public void cycle() {
		switch (typeSelection) {
		case RANKING:
			updateProbabilitiesRanking();
			break;
		case STOCHASTIC_UNIVERSAL:
			updateProbabilitiesStochastic();
			break;
		default:
			updateProbabilities();
			break;
		}
		reproduction(selection());
	}

	private void reproduction(ArrayList<Chromosome> list) {
		int i = 0;
		boolean[] mask = new boolean[list.size()];
		while (i < list.size() - 1) {
			int index1 = new Random().nextInt(list.size());
			while (!mask[index1]) {
				int index2 = new Random().nextInt(list.size());
				if (index1 != index2 && !mask[index2]) {
					// Mark the selected
					mask[index1] = mask[index2] = true;
					// Take the selected
					Chromosome child1 = list.get(index1);
					Chromosome child2 = list.get(index2);
					// Subtract the fitness from the total
					totalFitness -= child1.getFitness();
					totalFitness -= child2.getFitness();

					// Crossover
					switch (crossoverFunction) {
					case CROSSOVER_FUNCTION_1:
						crossover1(child1, child2);
						break;
					case CROSSOVER_FUNCTION_2:
						crossover2(child1, child2);
						break;
					case CROSSOVER_FUNCTION_3:
						crossover3(child1, child2);
						break;
					default:
						break;
					}

					// Mutar
					switch (mutFunction) {
					case MUTATION_FUNCTION_1:
						mutar1(child1);
						mutar1(child2);
						break;
					case MUTATION_FUNCTION_2:
						mutar2(child1);
						mutar2(child2);
						break;
					case MUTATION_FUNCTION_3:
						mutar3(child1);
						mutar3(child2);
					default:
						break;
					}

					add(chromosomes, child1);
					add(chromosomes, child2);

					i += 2;
				}
			}
		}
		if (list.size() % 2 == 1) {
			boolean found = false;
			for (int index = 0; !found && index < list.size(); index++) {
				if (found = !mask[index]) {
					add(chromosomes, list.get(index));
				}
			}
		}
	}

	private ArrayList<Chromosome> selection() {
		ArrayList<Chromosome> list;
		switch (typeSelection) {
		case RANKING:
		case STOCHASTIC_UNIVERSAL:
		case ROULETTE:
			list = selectRoulette();
			break;
		case TOURNAMENT:
			list = selectTournament();
			break;
		default:
			list = null;
			break;
		}
		return list;
	}

	private ArrayList<Chromosome> selectRoulette() {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(n);
		int k = 0;
		double pX = x > 0 ? chromosomes.get(x - 1).getpAccumulated() : 0.0;
		while (k < n) {
			double p = new Random().nextDouble();
			if (p <= pX) {
				continue;
			}
			int index = binarySearch2(chromosomes, p);
			if (index == chromosomes.size()) {
				index--;
			}
			add(list, chromosomes.remove(index));
			k++;
		}
		return list;
	}

	private ArrayList<Chromosome> selectTournament() {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(k);
		for (int time = 0; time < k; time++) {
			ArrayList<Chromosome> tournament = new ArrayList<Chromosome>(z);
			int i = 0;
			while (i < z && chromosomes.size() > x) {
				int index = new Random().nextInt(chromosomes.size());
				if (x <= index) {
					add(tournament, chromosomes.get(index));
					chromosomes.remove(index);
					i++;
				}
			}
			add(list, tournament.get(0));
			tournament.remove(0);
			for (Chromosome c : tournament) {
				add(chromosomes, c);
			}
		}
		return list;
	}

	private void crossover1(Chromosome c1, Chromosome c2) {
		final int LENGTH = Chromosome.LENGTH;
		for (int square = 0; square < LENGTH; square++) {
			int[] aux = c1.getSquare(square).clone();
			if (new Random().nextDouble() < crossover) {
				int crossingPoint = new Random().nextInt(LENGTH);
				for (int box = crossingPoint; box < LENGTH; box++) {
					c1.setGene(square, box, c2.getGene(square, box));
					c2.setGene(square, box, aux[box]);
				}
			}
		}
	}

	private void crossover2(Chromosome c1, Chromosome c2) {
		final int LENGTH = Chromosome.LENGTH;
		for (int square = 0; square < LENGTH; square++) {
			int[] aux = c1.getSquare(square).clone();
			if (new Random().nextDouble() < crossover) {
				c1.setSquare(c2.getSquare(square), square);
				c2.setSquare(aux, square);
			}
		}
	}

	private void crossover3(Chromosome c1, Chromosome c2) {
		final int LENGTH = Chromosome.LENGTH;
		Random r = new Random();
		for (int square = 0; square < LENGTH; square++) {

			if (r.nextDouble() < crossover) {
				int[] aux = c1.getSquare(square).clone();

				c1.setSquare(
						changeOrder(aux,
								getOrder(c2.getSquare(square), square), square,
								c1), square);
				c2.setSquare(
						changeOrder(c2.getSquare(square),
								getOrder(aux, square), square, c2), square);
			}
		}
	}

	private void crossover4(Chromosome c1, Chromosome c2) {
		final int LENGTH = Chromosome.LENGTH;
		Random r = new Random();
		for (int square = 0; square < LENGTH; square++) {
			if (r.nextDouble() < crossover) {
				int[] aux = c1.getSquare(square).clone();

				c1.setSquare(
						changeOrder(aux,
								getOrder(c2.getSquare(square), square), square,
								c1), square);

				c2.setSquare(
						changeOrder(c2.getSquare(square),
								getOrder(aux, square), square, c2), square);
			}
		}
	}

	private void mutar1(Chromosome c) {
		final int LENGTH = Chromosome.LENGTH;
		for (int square = 0; square < LENGTH; square++) {
			for (int box = 0; box < LENGTH; box++) {
				if (!blocked[square][box]
						&& new Random().nextDouble() < mutation) {
					int gene = new Random().nextInt(NUMS) + 1;
					c.setGene(square, box, gene);
				}
			}
		}
	}

	private void mutar2(Chromosome c) {
		final int LENGTH = Chromosome.LENGTH;
		for (int square = 0; square < LENGTH; square++) {
			for (int box = 0; box < LENGTH; box++) {
				if (!blocked[square][box]
						&& new Random().nextDouble() < mutation) {
					int index = new Random().nextInt(NUMS);
					if (!blocked[square][index]) {
						int aux = c.getGene(square, box);
						c.setGene(square, box, c.getGene(square, index));
						c.setGene(square, index, aux);
					}
				}
			}
		}
	}

	private void mutar3(Chromosome c) {
		final int LENGTH = Chromosome.LENGTH;
		Random r = new Random();
		for (int square = 0; square < LENGTH; square++) {
			for (int box = 0; box < LENGTH; box++) {
				int[] squareMask = getSquareMask(c, square);
				int[] rowMask = getRowMask(c, square, box);
				int[] colMask = getColMask(c, square, box);
				double mut = 0.0;
				int gene = c.getGene(square, box);
				if (gene != 0) {
					if (squareMask[gene - 1] > 1 || rowMask[gene - 1] > 1
							|| colMask[gene - 1] > 1) {
						mut = 1 - mutation;
					} else {
						mut = mutation;
					}
				}
				if (!blocked[square][box] && r.nextDouble() < mut) {
					boolean found = false;
					for (int index = 0; !found && index < LENGTH; index++) {
						found = squareMask[index] == 0;
						found &= rowMask[index] == 0;
						found &= colMask[index] == 0;
					}
					if (found) {
						int random = r.nextInt(NUMS);
						while (squareMask[random] != 0 || rowMask[random] != 0
								|| colMask[random] != 0) {
							random = r.nextInt(NUMS);
						}
						c.setGene(square, box, random + 1);
					}
				}
			}
		}
	}

	// Aux.

	public int[] getSquareMask(Chromosome c, int square) {
		final int LENGTH = Chromosome.LENGTH;
		int[] squareMask = new int[LENGTH];
		for (int box = 0; box < LENGTH; box++) {
			int gene = c.getGene(square, box);
			if (gene != 0) {
				squareMask[gene - 1]++;
			}
		}
		return squareMask;
	}

	public int[] getRowMask(Chromosome c, int square, int box) {
		final int LENGTH = Chromosome.LENGTH;
		final int SQUARE = Square.LENGTH;
		int square1;
		switch (square % 3) {
		case 0:
			square1 = square;
			break;
		case 1:
			square1 = square - 1;
			break;
		default:
			square1 = square - 2;
			break;
		}
		final int disp = (box / SQUARE) * SQUARE;
		int[] rowMask = new int[LENGTH];
		for (int i = 0; i < SQUARE; i++) {
			for (int j = 0; j < SQUARE; j++) {
				int gene = c.getGene(square1, j + disp);
				if (gene != 0) {
					rowMask[gene - 1]++;
				}
			}
			square1++;
		}
		return rowMask;
	}

	public int[] getColMask(Chromosome c, int square, int box) {
		final int LENGTH = Chromosome.LENGTH;
		final int SQUARE = Square.LENGTH;
		int square1;
		switch (square / 3) {
		case 0:
			square1 = square;
			break;
		case 1:
			square1 = square - SQUARE;
			break;
		default:
			square1 = square - 2 * SQUARE;
			break;
		}
		final int disp = box % SQUARE;
		int[] colMask = new int[LENGTH];
		for (int i = 0; i < SQUARE; i++) {
			for (int j = 0; j < SQUARE; j++) {
				int gene = c.getGene(square1, j * SQUARE + disp);
				if (gene != 0) {
					colMask[gene - 1]++;
				}
			}
			square1 += 3;
		}
		return colMask;
	}

	private int[] changeOrder(final int[] c, LinkedList<Integer> order,
			int square, Chromosome chro) {
		int min = 0;
		int[] ret = new int[Chromosome.LENGTH];
		int[] rmask;
		int[] cmask;

		while (!order.isEmpty()) {
			for (int i = 0; !order.isEmpty() && i < Chromosome.LENGTH; i++) {

				if (ret[i] == 0) {
					if (blocked[square][i]) {
						ret[i] = c[i];
					} else {
						rmask = getRowMask(chro, square, i);
						cmask = getRowMask(chro, square, i);
						int act = order.pollFirst();
						if (rmask[act - 1] + cmask[act - 1] <= min) {
							ret[i] = act;
						} else {
							order.addLast(act);
						}
					}

				}

			}
			min++;
		}

		return ret;
	}

	private LinkedList<Integer> getOrder(int[] c, int square) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < Chromosome.LENGTH; i++) {
			if (!blocked[square][i]) {
				list.add(c[i]);
			}
		}
		return list;
	}

	private int binarySearch(ArrayList<Chromosome> list, double aptitud) {
		return binarySearch(list, 0, list.size() - 1, aptitud);
	}

	private int binarySearch(ArrayList<Chromosome> list, int s, int e,
			double fitness) {
		if (s > e) {
			return s;
		}
		int medium = (s + e) / 2;
		double mediumFitness = list.get(medium).getFitness();
		if (mediumFitness == fitness) {
			return medium;
		} else if (mediumFitness > fitness) {
			return binarySearch(list, medium + 1, e, fitness);
		} else {
			return binarySearch(list, s, medium - 1, fitness);
		}
	}

	private int binarySearch2(ArrayList<Chromosome> list, double p) {
		return binarySearch2(list, 0, list.size() - 1, p);
	}

	private int binarySearch2(ArrayList<Chromosome> list, int s, int e, double p) {
		if (s > e) {
			return s;
		}
		int medium = (s + e) / 2;
		double pMedium = list.get(medium).getpAccumulated();
		if (pMedium == p) {
			return medium;
		} else if (pMedium > p) {
			return binarySearch2(list, s, medium - 1, p);
		} else {
			return binarySearch2(list, medium + 1, e, p);
		}
	}

	private void add(ArrayList<Chromosome> list, Chromosome chromosome) {
		chromosome.evaluate();
		totalFitness += chromosome.getFitness();
		if (list.isEmpty()) {
			list.add(chromosome);
		} else {
			list.add(binarySearch(list, chromosome.getFitness()), chromosome);
		}
	}

	private void updateProbabilities() {
		Chromosome c = chromosomes.get(0);
		c.setpSelection(c.getFitness() / totalFitness);
		c.setpAccumulated(c.getpSelection());
		for (int i = 1; i < chromosomes.size() - 1; i++) {
			c = chromosomes.get(i);
			double pSelection = c.getFitness() / totalFitness;
			c.setpSelection(pSelection);
			c.setpAccumulated(pSelection
					+ chromosomes.get(i - 1).getpAccumulated());
		}
		c = chromosomes.get(chromosomes.size() - 1);
		c.setpSelection(c.getFitness() / totalFitness);
		c.setpAccumulated(1.0);
	}

	private void updateProbabilitiesRanking() {
		// P = 2 - PresionSelectiva + 2(PS - 1) * (pos - 1) / (tot - 1)
		int i = 0;
		double ps = 2.0;
		double prob;
		for (Chromosome c : chromosomes) {
			prob = 2 - ps + 2 * (ps - 1) * ((i - 1) / (population - 1));
			c.setpSelection(prob);
			i++;
		}
	}

	private void updateProbabilitiesStochastic() {
		// P = 2 - PresionSelectiva + 2(PS - 1) * (pos - 1) / (tot - 1)
		double pAcum = 1.0;
		double prob = 1 / population;
		for (Chromosome c : chromosomes) {
			c.setpSelection(prob);
			pAcum += prob;
			c.setpAccumulated(pAcum);
		}
	}

	public Sudoku getSudoku() {
		return new Sudoku(chromosomes.get(0).getGenes());
	}
}
